The need for optimization of systems arises in a broad range of technological and industrial areas. Examples of such a need include the assignment of transmission facilities in telephone transmission systems, oil tanker scheduling, control of the product mix in a factory, deployment of industrial equipment, inventory control, and others. In these examples a plurality of essentially like parameters are controlled to achieve an optimum behavior or result. Sometimes, the parameters controlling the behavior of a system have many different characteristics but their effect is the same; to wit they combine to define the behavior of the system. An example of that is the airline scheduling task. Not only must one take account of such matters as aircraft, crew, and fuel availability at particular airports, but it is also desirable to account for different costs at different locations, the permissible routes, desirable route patterns, arrival and departure time considerations vis-a-vis one's own airline and competitor airlines, the prevailing travel patterns to and from different cities, etc. Two common denominators of all of these applications is the existence of many parameters or variables that can be controlled, and the presence of an objective--to select values for the variables so that, in combination, an optimum result is achieved.
The relationships describing the permissible values of the various variables and their relationship to each other form a set of constraint relationships. Optimization decisions are typically subject to constraints. Resources, for example, are always limited in overall availability and, sometimes, the usefulness of a particular resource in a specific application is limited. The challenge, then, is to select values of the parameters of the system so as to satisfy all of the constraints and concurrently optimize its behavior, i.e., bring the level of "goodness" of the objective function to its maximum attainable level. Stated in other words, given a system where resources are limited, the objective is to allocate resources in such a manner so as to optimize the system's performance.
One method of characterizing optimization tasks is via the linear programming model. Such a model consists of a set of linear equalities and inequalities that represent the quantitative relationships between the various possible system parameters, their constraints, and their costs (or benefits).
Some optimization tasks cannot be represented by such systems of linear relationships. They involve higher powers of the unknowns or other nonlinearities in the relationships and hence are not encompassed by the linear programming model.
It should be noted that the optimization tasks discussed above pertain to real physical problems for which businessmen require solutions. It may also be noted that it is not unusual for a physical problem to be represented by mathematical expressions from which parameter values can be specified for use in the physical world to construct or operate a physical system. Typical prior art examples of the use of mathematical models to characterize physical systems are the construction of complex filters, design and characterization of radio antennas, and control of rubber-molding operations.
At one time, artisans were unable to explicitly solve many of the optimization tasks that were facing them. To compensate for that inability, people used intuition and experience to arrive at what they felt was a preferred assignment of parameter values. Businessmen who were good at it prospered, and those who were not good at it failed. More recently, quantitative tools have become available to assist businessmen in these decision-making activities. For example, manufacturing plants use linear programming models to control production schedules and inventory levels that will satisfy sales demands and, at the same time, minimize production and inventory costs. Similarly, the AT&T communication network uses linear programming models to route telephone traffic over a network of transmission facilities so that the entire traffic demand is satisfied, transmission costs are minimized, and at the same time, no transmission links are overloaded.
The best known prior art approach to solving allocation problems posed as linear programming models is known as the simplex method. It was invented by George B. Dantzig in 1947, and described in Linear Programming and Extensions, by George B. Dantzig, Princeton University Press, Princeton, New Jersey, 1963. In the simplex method, the first step is to select an initial feasible allocation as a starting point. The simplex method gives a particular method for identifying successive new allocations, where each new allocation improves the objective function compared to the immediately previous identified allocation, and the process is repeated until the identified allocation can no longer be improved.
The operation of the simplex method can be illustrated diagrammatically. In two-dimensional systems the solutions of a set of linear constraint relationships are given by a polygon of feasible solutions. In a three-dimensional problem, linear constraint relationships form a three dimensional polytope of feasible solutions. As may be expected, optimization tasks with more than three variables form higher dimensional polytopes. FIG. 1 depicts a polytope contained within a multi-dimensional hyperspace (the representation is actually shown in three dimensions for lack of means to represent higher dimensions). It has a plurality of facets, such as facet 11, and each of the facets is a graphical representation of a portion of one of the constraint relationships in the formal linear programming model. That is, each linear constraint defines a hyperplane in the multi-dimensional space of polytope 10, and a portion of that plane forms a facet of polytope 10. Polytope 10 is convex, in the sense that a line joining any two points of polytope 10 lies within or on the surface of the polytope.
It is well known that there exists a solution of a linear programming model which maximizes (or minimizes) an objective function, and that the solution lies at a vertex of polytope 10. The strategy of the simplex method is to successively identify from each vertex the adjacent vertices of polytope 10, and select each new vertex (each representing a new feasible solution of the optimization task under consideration) so as to bring the feasible solution closer, as measured by the objective function, to the optimum point 21. In FIG. 1, the simplex method might first identify vertex 12 and then move in a path 13 from vertex to vertex (14 through 20) until arriving at the optimum point 21.
The simplex method is thus constrained to move on the surface of polytope 10 from one vertex of polytope 10 to an adjacent vertex along an edge. In linear programming problems involving thousands, hundreds of thousands, or even millions of variables, the number of vertices on the polytope increases correspondingly, and so does the length of path 13. Moreover, there are so-called "worst case" problems where the topology of the polytope is such that a substantial fraction of the vertices must be traversed to reach the optimum vertex.
As a result of these and other factors, the average computation time needed to solve a linear programming model by the simplex method appears to grow at least proportionally to the square of the number of constraints in the model. For even moderately-sized allocation problems, this time is often so large that using the simplex method is simply not practical. This occurs, for example, where the constraints change before an optimum allocation can be computed, or the computation facilities necessary to optimize allocations using the model are simply not available at a reasonable cost. Optimum allocations could not generally be made in "real time" (i.e., sufficiently fast) to provide more or less continuous control of an ongoing process, system or apparatus.
To overcome the computational difficulties in the above and other methods, N. K. Karmarkar invented a new method, and apparatus for carrying out his method, that substantially improves the process of resource allocation. In accordance with Karmarkar's method, which is disclosed in U.S. patent application Ser. No. 725,342 filed Apr. 19, 1985, a starting feasible solution is selected within polytope 10, and a series of moves are made in the direction that, locally, points in the direction of greatest change toward the optimum vertex of the polytope. A step of computable size is then taken in that direction, and the process repeats until a point is reached that is close enough to the desired optimum point to permit identification of the optimum point.
Describing the Karmarkar invention more specifically, a point in the interior of polytope 10 is used as the starting point. Using a change of variables which preserves linearity and convexity, the variables in the linear programming model are transformed so that the starting point is substantially at the center of the transformed polytope and all of the facets are more or less equidistant from the center. The objective function is also transformed. The next point is selected by moving in the direction of steepest change in the transformed objective function by a distance (in a straight line) constrained by the boundaries of the polytope (to avoid leaving the polytope interior). Finally, an inverse transformation is performed on the new allocation point to return that point to the original variables, i.e., to the space of the original polytope. Using the transformed new point as a new starting point, the entire process is repeated.
Karmarkar describes two related "rescaling" transformations for moving a point to the center of the polytope. The first method uses a projective transformation, and the second method uses an affine transformation. These lead to closely related procedures, which we call projective scaling and affine scaling, respectively. The projective scaling procedure is described in detail in N. K. Karmarkar's paper, "A New Polynomial Time Algorithm for Linear Programming", Combinatorica, Vol. 4, No. 4, 1984, pp. 373-395, and the affine scaling method is described in the aforementioned N. Karmarkar '342 application and in that of Vanderbei, filed Apr. 11, 1986 and bearing the Ser. No. 851,120.
The advantages of the Karmarkar invention derive primarily from the fact that each step is radial within the polytope rather than circumferential on the polytope surface and, therefore, many fewer steps are necessary to converge on the optimum point.
Still, even in Karmarkar's method and apparatus a substantial number of iterations is required when the number of variables to be controlled is very large. Also, the calculations that need to be performed are not trivial because they involve transformations of very large matrices. Fortunately, in most applications the matrices are rather sparse because most of the coefficients of most of the variables are zero. This sparsity permits simplifications to be made which result in substantial improvements in performing resource allocation assignments with Karmarkar's apparatus and method.
The number of iterations that is required in Karmarkar's method is related to the number of variables and to the chosen size for each step. But because the step taken is a straight line which only locally points in the direction of steepest change in the objective function, it is clear that large step sizes may not be taken for fear of moving away from the shortest path toward the optimum point, and possibly causing the process to converge even slower than with smaller steps.